# -*- coding: utf-8 -*-

''' Autor: Neuza Figueira - n.º 6036 '''

import sys
from random import uniform
from time import clock
import math
import matplotlib.pyplot as plt

class HeapSort():
        ''' Class to handle Heapsort implementation and testing.'''
        
        def max_heapify(self, A, i):
                '''Procedure that maintains the max-heap property.'''
                '''@param A -> Input array.'''
                '''@param i -> Index i into the array.'''
                global HEAPSIZE
                
                left = 2 * i
                right = left + 1

                if (left <= HEAPSIZE and A[left] > A[i]):
                    largest = left
                    pass
                else:
                    largest = i
                    pass

                if (right <= HEAPSIZE and A[right] > A[largest]):
                    largest = right
                    pass

                if (largest != i):
                    A[i], A[largest] = A[largest], A[i]
                    self.max_heapify(A, largest)
                    pass
                pass


                
        def build_max_heap(self, A):
        
            '''Procedure that produces a max-heap from an unordered input array.'''
            '''@param A -> Input array.'''
            global HEAPSIZE
            HEAPSIZE = len(A) - 1 
            for i in range((HEAPSIZE / 2), 0, -1):
                self.max_heapify(A, i)
                pass
            pass


        def heap_sort(self, A):
            '''Python Implementation of Heapsort.'''
            '''@param A -> List to sort.'''
            global HEAPSIZE
            self.build_max_heap(A)
            for i in range((len(A) - 1), 0, -1):
                A[0], A[i] = A[i], A[0]
                HEAPSIZE = HEAPSIZE - 1
                self.max_heapify(A, 0)
                pass
                return A
            pass


        def testHeapSort(self):
                '''Testing the complexity of Heapsort.'''
                Z = range(50, 1050, 50)
                T = []
                M = 50
                for n in Z:
                    A = [ uniform(0.0, 1.0) for k in xrange(n)]
                    tempos = []
                    for k in range(M):
                        t1 = clock()
                        self.heap_sort(A)
                        t2 = clock()
                        tempos.append(t2-t1)
                        
                    media = reduce(lambda x, y: x + y, tempos) / len(tempos)
                    var = reduce(lambda x, y: x + (y-media)**2, [0] + tempos) / len(tempos)
                    
                    T.append((n,media, var))

                X = [n for n, media, var in T]
                Y = [media for n, media, var in T]
                ct = 11e6

                Z = [(n * math.log(n)) / ct for n, media, var in T]


                plt.grid(True)
                plt.ylabel(u'T(n) - tempo de execução médio em segundos')
                plt.xlabel(u'n - número de elementos')
                plt.plot(X,Y,'rs', label="resultado experimental")
                plt.plot(X, Z, 'b^', label=u"previsão teórica")
                plt.legend()
                plt.show()
                pass


